package _动态规划;

@SuppressWarnings("all")
public class State_DP {

    // 121：买卖股票的最佳时机 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        // 双指针动态规划
        // min: 股票的最低价
        // max：获取的最大利润
        int min = prices[0], max = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            max = Math.max(max, prices[i] - min);
        }
        return max;
    }

    //  122： 买卖股票的最佳时机II ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
    public int maxProfitII_(int[] prices) {
        int reve = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                reve += prices[i] - prices[i - 1];
            }
        }
        return reve;
    }

    // 从状态机的角度来求解
    public int maxProfitII(int[] prices) {
        int reve = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                reve += prices[i] - prices[i - 1];
            }
        }
        return reve;
    }

    // 309：买卖股票的最佳时机（含冷冻期）：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
    /*
    *  状态定义：
            dp[i][0] 表示第 i 天不持有股票的最大利润。
            dp[i][1] 表示第 i 天持有股票的最大利润。
            dp[i][2] 表示第 i 天处于冷冻期的最大利润（即前一天卖出股票后，今天不能买入股票）。
       状态转移：
            dp[i][0] = max(dp[i-1][0], dp[i-1][2])              说明今天不持有股票，可以选择从前一天不持有或冷冻期恢复。
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])  说明今天持有股票，可以选择从前一天持有或从前一天不持有并买入股票。
            dp[i][2] = dp[i-1][1] + prices[i]                   说明今天是冷冻期，表示前一天持有股票，今天卖出
    * */
    public int maxProfitIII(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        // 初始化dp变量
        int dp0 = 0;          // 第i天不持有股票的最大利润
        int dp1 = -prices[0]; // 第i天持有股票的最大利润
        int dp2 = 0;          // 第i天冷冻期的最大利润

        for (int i = 1; i < prices.length; i++) {
            // 计算今天的状态
            int newDp0 = Math.max(dp0, dp2); // 今天不持有股票
            int newDp1 = Math.max(dp1, dp0 - prices[i]); // 今天持有股票
            int newDp2 = dp1 + prices[i]; // 今天进入冷冻期

            dp0 = newDp0;
            dp1 = newDp1;
            dp2 = newDp2;
        }
        return Math.max(dp0, dp2);
    }

    // 714：含手续费：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
    public int maxProfit_714(int[] prices, int fee) {
        int dp0 = 0;                //  不持有股票
        int dp1 = -prices[0];       //  持有股票
        for (int i = 1; i < prices.length; i++) {
            int dp00 = Math.max(dp0, dp1 + prices[i] - fee);
            int dp11 = Math.max(dp1, dp0 - prices[i]);
            dp0 = dp00;
            dp1 = dp11;
        }
        return Math.max(dp0, dp1);
    }

    // 188：买卖股票的最佳时机（最多 K 次交易）：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
    // 买入——卖出：算一次交易
    // dp[i][j][0]：第 i 天，最多进行 j 次交易，不持股时的最大利润；
    // dp[i][j][1]：第 i 天，最多进行 j 次交易，持股时的最大利润。
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (prices == null || n == 0) return 0;
        if (k >= n / 2) {
            int reve = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] > prices[i - 1]) {
                    reve += prices[i] - prices[i - 1];
                }
            }
            return reve;
        }
        int[][] dp = new int[k + 1][2];
        // dp数组初始化
        for (int j = 0; j <= k; j++) {
            dp[j][0] = 0;
            dp[j][1] = -prices[0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = Math.max(dp[j][1], dp[j - 1][0] - prices[i]);   //买入表示开启一轮新的交易
            }
        }
        return dp[k][0];
    }

}
















